{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Arithmetic Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestArithSeqLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长等差数列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>，返回 <code>nums</code>&nbsp;中最长等差子序列的<strong>长度</strong>。</p>\n",
    "\n",
    "<p>回想一下，<code>nums</code> 的子序列是一个列表&nbsp;<code>nums[i<sub>1</sub>], nums[i<sub>2</sub>], ..., nums[i<sub>k</sub>]</code> ，且&nbsp;<code>0 &lt;= i<sub>1</sub> &lt; i<sub>2</sub> &lt; ... &lt; i<sub>k</sub> &lt;= nums.length - 1</code>。并且如果&nbsp;<code>seq[i+1] - seq[i]</code>(&nbsp;<code>0 &lt;= i &lt; seq.length - 1</code>) 的值都相同，那么序列&nbsp;<code>seq</code>&nbsp;是等差的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,6,9,12]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释： </strong>\n",
    "整个数组是公差为 3 的等差数列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [9,4,7,2,10]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "最长的等差子序列是 [4,7,10]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [20,1,15,3,10,5,8]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "最长的等差子序列是 [20,15,10,5]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-arithmetic-subsequence](https://leetcode.cn/problems/longest-arithmetic-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-arithmetic-subsequence](https://leetcode.cn/problems/longest-arithmetic-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,9,12]', '[9,4,7,2,10]', '[20,1,15,3,10,5,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A):\n",
    "        dp  = {}\n",
    "        for i in range(len(A)):\n",
    "            for j in range(i+1,len(A)):\n",
    "                step = A[j]-A[i]\n",
    "                dp[step,j] = max(dp.get((step,j),0), dp.get((step,i),1)+1)\n",
    "        return max(dp.values())\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        if n < 1:\n",
    "            return 0\n",
    "        num2idx_dict = dict()\n",
    "        for i, num in enumerate(A):\n",
    "            if num not in num2idx_dict:\n",
    "                num2idx_dict[num] = [i]\n",
    "            else:\n",
    "                num2idx_dict[num].append(i)\n",
    "\n",
    "        max_len = 2\n",
    "        for i in range(0, n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                diff = A[j] - A[i]\n",
    "                k = j\n",
    "                length = 2\n",
    "                while True:\n",
    "                    next_val = A[k] + diff\n",
    "                    idx_list = num2idx_dict.get(next_val, [])\n",
    "                    idx_next = None\n",
    "                    for idx in idx_list:\n",
    "                        if idx <= k:\n",
    "                            continue\n",
    "                        idx_next = idx\n",
    "                        break\n",
    "                    if idx_next is not None:\n",
    "                        length += 1\n",
    "                        max_len = max(max_len, length)\n",
    "                        k = idx_next\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        max_res = -1\n",
    "\n",
    "        max_A = max(A)\n",
    "        min_A = min(A)\n",
    "\n",
    "        for i in range(min_A-max_A, max_A-min_A):\n",
    "            d = {}\n",
    "            for a in A:\n",
    "                d[a] = d.get(a - i, 0) + 1\n",
    "            max_tmp = max(d.values())\n",
    "            if max_res < max_tmp:\n",
    "                max_res = max_tmp\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        diffs = [-i-1 for i in range(250)]\n",
    "        diffs += [0]\n",
    "        diffs += [i+1 for i in range(250)]\n",
    "        result = 2\n",
    "        for diff in diffs:\n",
    "            count = {}\n",
    "            for i in range(len(nums)):\n",
    "                if(nums[i] - diff in count):\n",
    "                    count[nums[i]] = count[nums[i] - diff] +1\n",
    "                else:\n",
    "                    count[nums[i]] = 1\n",
    "            result = max(result,max(count.values()))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        minv, maxv = min(nums), max(nums)\n",
    "        diff = maxv - minv\n",
    "        longest_len = 1\n",
    "\n",
    "        for d in range(-diff, diff + 1):\n",
    "            f = dict()\n",
    "            for num in nums:\n",
    "                if(prev := num - d) in f:\n",
    "                    f[num] = max(f.get(num, 0), f[prev] + 1)\n",
    "                    longest_len = max(longest_len, f[num])\n",
    "                f[num] = max(f.get(num, 0), 1)\n",
    "        return longest_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        if not A:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        D = defaultdict(list)\n",
    "        for i,j in enumerate(A):\n",
    "            D[j].append(i)\n",
    "        for i in range(len(A)):\n",
    "            for j in range(i+1, len(A)):\n",
    "                cl = 2\n",
    "                j1 = j\n",
    "                i1 = i\n",
    "                while D[2*A[j1]-A[i1]]:\n",
    "                    k = False\n",
    "                    for p in D[2*A[j1]-A[i1]]:\n",
    "                        if p>j1:\n",
    "                            k = True\n",
    "                            i1 = j1\n",
    "                            j1 = p\n",
    "                            cl += 1\n",
    "                            break\n",
    "                    if not k:\n",
    "                        break\n",
    "                if cl>ans:\n",
    "                    ans = cl\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def search(self, l, r, t):\n",
    "    #     if l > r:\n",
    "    #         return l\n",
    "    #     m = (l+r)//2\n",
    "    #     if t > self.h[m]:\n",
    "    #         return self.search(m+1, r, t)\n",
    "    #     return self.search(l, m-1, t)\n",
    "\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        self.h = h = dict(zip(set(nums), range(n)))\n",
    "        \n",
    "        dp = [[0]*1001 for _ in range(len(h))]\n",
    "\n",
    "        m = 0\n",
    "        for i in range(1, n):\n",
    "            dp1 = dp[h[nums[i]]].copy()\n",
    "            for j in range(i):\n",
    "                v = max(2, dp[h[nums[j]]][nums[i]-nums[j]]+1)\n",
    "                dp1[nums[i]-nums[j]] = v\n",
    "                m = max(m, v)\n",
    "            dp[h[nums[i]]] = dp1\n",
    "\n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0] * 1001 for _ in range(501)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(1001):\n",
    "                d = nums[i] - (j - 500)\n",
    "                if d >= 0 and d <= 500:\n",
    "                    dp[nums[i]][j] = dp[d][j] + 1\n",
    "                else:\n",
    "                    dp[nums[i]][j] = 1\n",
    "                ans = max(ans, dp[nums[i]][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        ones = set()\n",
    "        dis = set()\n",
    "        ans = 1\n",
    "        dp = dict()\n",
    "\n",
    "        for num in nums:\n",
    "            for last in ones:\n",
    "                if (d := num - last) not in dp:\n",
    "                    dp[d] = {}\n",
    "                    dp[d][num] = 2\n",
    "                else:\n",
    "                    dp[d][num] = dp[d].get(num - d, 1) + 1\n",
    "                ans = max(ans, dp[d][num])\n",
    "            ones.add(num)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        res = (0,0,0)\n",
    "        hashmap = collections.defaultdict(dict)\n",
    "        counter = collections.defaultdict(int)\n",
    "        countMax = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            n = nums[i]\n",
    "            counter[n] +=1\n",
    "            countMax = max(countMax, counter[n])\n",
    "            for j in range(i):\n",
    "                difference = n - nums[j]\n",
    "                if difference == 0:\n",
    "                    continue\n",
    "                if nums[j] in hashmap[difference]:\n",
    "                    hashmap[difference][n] = hashmap[difference][nums[j]] + 1\n",
    "                else:\n",
    "                    hashmap[difference][n] = 2\n",
    "                res = max(res, (hashmap[difference][n], difference, n))\n",
    "        \n",
    "        return max(res[0], countMax)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        curd = 500\n",
    "        n = len(nums)\n",
    "        f = [[0] * 1010 for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            f[0][curd] = 1\n",
    "        \n",
    "        dif = max(nums) - min(nums)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                f[i][nums[i] - nums[j] + curd] = max(f[j][nums[i] - nums[j] + curd] + 1, 2)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(-dif, dif + 1):\n",
    "                res = max(res, f[i][j + curd])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find_k(self, idxs, r):\n",
    "        k = bisect_left(idxs, r)\n",
    "        return idxs[k - 1] if k > 0 else -1\n",
    "\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 2: return 2\n",
    "        mapping = defaultdict(lambda: [])\n",
    "        for idx, x in enumerate(nums):\n",
    "            mapping[x].append(idx)\n",
    "        \n",
    "        # f[i][j] 以 a[i], a[j] 为结尾的等差序列的最大长度\n",
    "        f = [[2] * n for _ in range(n)]\n",
    "        res = 2\n",
    "        for i in range(1, n):\n",
    "            for j in range(i+1, n):\n",
    "                delta = nums[j] - nums[i]\n",
    "                target_k = nums[i] - delta\n",
    "                if target_k not in mapping:\n",
    "                    continue\n",
    "                k = self.find_k(mapping[target_k], i)\n",
    "                if k > -1:\n",
    "                    f[i][j] = f[k][i] + 1\n",
    "                    res = max(res, f[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0 for _ in range(n-1)] for _ in range(n)]\n",
    "        mem = {}\n",
    "        for i in range(n):\n",
    "            if nums[i] not in mem:\n",
    "                mem[nums[i]] = []\n",
    "            bisect.insort(mem[nums[i]], i)\n",
    "            for j in range(i-1, -1, -1):\n",
    "                dp[i][j] = 2\n",
    "        maxlen = 2\n",
    "        for i in range(2, n):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                z = mem.get(2*nums[j]-nums[i], [])\n",
    "                if z:\n",
    "                    index = bisect.bisect_left(z, j)\n",
    "                    if index:\n",
    "                        dp[i][j] = dp[j][z[index-1]]+1\n",
    "                        maxlen = max(maxlen, dp[i][j])\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dp=[[0 for i in range(1500)]for j in range(len(nums))]\n",
    "        res=float('-inf')\n",
    "        for i in range(1,len(nums)):\n",
    "            for j in range(i):\n",
    "                diff=nums[i]-nums[j]\n",
    "                dp[i][diff]=dp[j][diff]+1\n",
    "                res=max(res,dp[i][diff])\n",
    "        return res+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        from collections import defaultdict\n",
    "\n",
    "        # Solution: Dynamic Programming\n",
    "        n = len(nums)\n",
    "\n",
    "        mp = defaultdict(list)\n",
    "\n",
    "        # Step 1: Construct the state-transition matrix\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        # Step 2: Set the initial state\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i):\n",
    "                dp[i][j] = 2\n",
    "        \n",
    "        # Step 3: Define the state-transition matrix\n",
    "        for i, num in enumerate(nums):\n",
    "            for j, prev_num in enumerate(nums[:i]):\n",
    "                diff = num - prev_num\n",
    "\n",
    "                if diff == 0:\n",
    "                    dp[i][j] = 1 + len(mp[num])\n",
    "                else:\n",
    "                    prev_prev_num = prev_num - diff\n",
    "                    for k in mp[prev_prev_num]:\n",
    "                        dp[i][j] = max(dp[i][j], 1 + dp[j][k])\n",
    "            mp[num].append(i)\n",
    "\n",
    "        return max([max(d) for d in dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        dp = defaultdict(lambda :defaultdict(int))\n",
    "        ans = 0\n",
    "        for i , num in enumerate(nums):\n",
    "            label = True\n",
    "            for j in range(i):\n",
    "                if num == nums[j] and not label:continue\n",
    "                dp[num][num-nums[j]] = dp[nums[j]][num-nums[j]] + 1\n",
    "                ans = max(ans,dp[num][num-nums[j]])\n",
    "                if num == nums[j]:\n",
    "                    label = False\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        M, N = 2020, len(nums)\n",
    "        f = [[1] * M for _ in range(N)]\n",
    "        ans = 0\n",
    "        for i in range(N):\n",
    "            for j in range(i):\n",
    "                x = nums[i] - nums[j] + 1010\n",
    "                f[i][x] = f[j][x] + 1\n",
    "                ans = max(ans, f[i][x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: # 方法二：二维\n",
    "    def longestArithSeqLength(self, a: List[int]) -> int:\n",
    "        f = [{} for _ in range(len(a))]\n",
    "        for i, x in enumerate(a):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                d = x - a[j]  # 公差\n",
    "                if d not in f[i]:\n",
    "                    f[i][d] = f[j].get(d, 1) + 1\n",
    "        return max(max(d.values()) for d in f[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        max_diff = max(nums) - min(nums)\n",
    "        diff_list = [dict() for _ in range(max_diff*2+1)]\n",
    "        max_len = 1\n",
    "        for i in range(n):\n",
    "            for j in range(max_diff*2+1):\n",
    "                diff = j - max_diff\n",
    "                if nums[i]-diff not in diff_list[j]:\n",
    "                    diff_list[j][nums[i]] = 1\n",
    "                else:\n",
    "                    diff_list[j][nums[i]] = diff_list[j][nums[i]-diff] + 1\n",
    "                    max_len = max(max_len, diff_list[j][nums[i]])\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        \n",
    "        L = len(nums)\n",
    "        t = [{} for _ in range(L)]\n",
    "\n",
    "        for i in range(1,L):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                if d==26:\n",
    "                    d = 26\n",
    "                if d in t[j]:\n",
    "                    t[i][d] = t[j][d]+1\n",
    "                else:\n",
    "                    t[i][d]=2\n",
    "        a = []\n",
    "        for i in range(L):\n",
    "            a.extend(list(t[i].values()))\n",
    "\n",
    "        a.sort()\n",
    "        return a[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        seem = set()\n",
    "        counts = {}\n",
    "        for k in nums:\n",
    "            for j in seem:\n",
    "                d = j - k\n",
    "                counts[(k, d)] = counts.get((j, d), 1) + 1\n",
    "            seem.add(k)\n",
    "        return max(counts.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dp = dict()\n",
    "        set_pre = set()\n",
    "        for i, cur in enumerate(nums[1:], 1):\n",
    "            set_pre.add(nums[i-1])\n",
    "            for pre in set_pre:\n",
    "                d = cur-pre\n",
    "                k_pre, k_cur = (pre,d), (cur,d)\n",
    "                if k_pre not in dp:\n",
    "                    dp[k_cur] = 2\n",
    "                else:\n",
    "                    dp[k_cur] = dp[k_pre]+1\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np \n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        res = np.zeros((m, 1000))\n",
    "\n",
    "        # init condition\n",
    "        # first element corresponds to the length \n",
    "        ans = 1\n",
    "        for i in range(-500, 500):\n",
    "            res[0, i] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                # if nums[j] is the last element of arith seq\n",
    "                if res[j, d] > 0:\n",
    "                    res[i, d] = res[j, d] + 1\n",
    "                else:\n",
    "                    res[i, d] = 2\n",
    "\n",
    "                ans = max(ans, res[i, d])\n",
    "\n",
    "\n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dp = [defaultdict(int) for i in range(len(nums))]\n",
    "        for i in range(1,len(nums)):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] = dp[j][d] + 1\n",
    "        return max([max(i.values()) for i in dp]) + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(lambda: 1) for _ in range(n)]\n",
    "        max_length = 0\n",
    "\n",
    "        for i, a in enumerate(nums):\n",
    "            for j, b in enumerate(nums[:i]):\n",
    "                diff = a - b\n",
    "                dp[i][diff] = dp[j][diff] + 1\n",
    "                if max_length < dp[i][diff]:\n",
    "                    max_length = dp[i][diff]\n",
    "        \n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for i in range(n)]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                dp[i][nums[i]-nums[j]] = dp[j][nums[i]-nums[j]] + 1\n",
    "\n",
    "        res = 0\n",
    "        for i in dp:\n",
    "            res = max(max(i.values()) + 1, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        _i = dict()\n",
    "        _min = 1000\n",
    "        _max = -1\n",
    "        for i, v in enumerate(nums):\n",
    "            _min = min(_min, v)\n",
    "            _max = max(_max, v)\n",
    "            if v not in _i:\n",
    "                _i[v] = []\n",
    "            _i[v].append(i)\n",
    "        \n",
    "        def index(v):\n",
    "            if v in _i:\n",
    "                return _i[v]\n",
    "            else:\n",
    "                return []\n",
    "        \n",
    "        D = _max - _min\n",
    "        from numpy import zeros\n",
    "        dp = zeros((len(nums), 2 * D + 1))\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for d in range(2 * D + 1):\n",
    "                indies = index(nums[i] - (d - D))\n",
    "                if len(indies):\n",
    "                    insert_point = bisect_left(indies, i) - 1\n",
    "                    if insert_point < 0:\n",
    "                        dp[i, d] = 1\n",
    "                    else:\n",
    "                        dp[i, d] = dp[indies[insert_point], d] + 1\n",
    "                else:\n",
    "                    dp[i, d] = 1\n",
    "                ans = max(ans, dp[i, d])\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(lambda :defaultdict(int))\n",
    "        max_len = 1\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                diff = nums[j] - nums[i]\n",
    "                d[diff][j] = d[diff][i] + 1\n",
    "                # if i in d[diff]:\n",
    "                #     d[diff][j] = d[diff][i] + 1\n",
    "                max_len = max(max_len, d[diff][j])\n",
    "                # else:\n",
    "                #     d[diff][j] = 2\n",
    "        \n",
    "        return max_len +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        d = defaultdict(list)\n",
    "        for i, n in enumerate(nums):\n",
    "            d[n].append(i)\n",
    "        \n",
    "        res = 2\n",
    "        \n",
    "        visited = set()\n",
    "\n",
    "        for j in range(1, len(nums)):\n",
    "            for i in range(j):\n",
    "                diff = nums[j] - nums[i]\n",
    "                if (nums[i], diff) in visited and (nums[j], diff) in visited:\n",
    "                    continue\n",
    "                visited.add((nums[i], diff))\n",
    "                visited.add((nums[j], diff))\n",
    "                l = 2\n",
    "                goal = nums[j] + diff\n",
    "                index = j+1\n",
    "                while goal in d:\n",
    "                    k = bisect.bisect_left(d[goal], index)\n",
    "                    if k < len(d[goal]):\n",
    "                        index = d[goal][k]+1\n",
    "                        visited.add((goal, diff))\n",
    "                        l += 1\n",
    "                        res = max(res, l)\n",
    "                        goal = goal + diff\n",
    "\n",
    "                    else:\n",
    "                        break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ma = 0\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        count = [collections.defaultdict(int) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                tmp1 = nums[i] -  nums[j]\n",
    "                tmp2 = count[j][tmp1]\n",
    "                tmp3 = tmp2 + 1\n",
    "                count[i][tmp1] = tmp3\n",
    "                dp[i][j] = tmp3\n",
    "                ma = max(ma,tmp3)\n",
    "        return ma + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        res = 2\n",
    "        if l<=2:\n",
    "            return l \n",
    "        d = collections.defaultdict(lambda: collections.defaultdict(lambda: 1))\n",
    "        dp = [[0 for _ in range(l)] for _ in range(l)]\n",
    "        for i in range(l):\n",
    "            dp[i][i] = 1\n",
    "            if i!=0:\n",
    "                dp[0][i] = 2\n",
    "                cha = nums[i]-nums[0]\n",
    "                d[i][cha] = 2\n",
    "        dp[0][0] = 1\n",
    "        for i in range(1,l-1):\n",
    "            for j in range(i+1,l):\n",
    "                cha = nums[j] - nums[i]\n",
    "                dp[i][j] = d[i][cha] + 1\n",
    "                d[j][cha] = max(d[j][cha], dp[i][j])\n",
    "                res = max(res, dp[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(lambda: defaultdict(int))\n",
    "        p = max(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            cur = nums[i - 1]\n",
    "            for j in range(-p, p + 1):\n",
    "                pre = nums[i - 1] - j\n",
    "                d[cur][j] = d[pre][j] + 1\n",
    "        ans = 0\n",
    "        for k, v in d.items():\n",
    "            ans = max(max(v.values()), ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        max_num, min_num = max(nums), min(nums)\n",
    "        diff_bound_left = min_num-max_num\n",
    "        diff_bound_right = max_num-min_num\n",
    "\n",
    "        d = [defaultdict(int) for _ in range(diff_bound_left, diff_bound_right+1)]  # 每个差用一个dict存\n",
    "\n",
    "        rs = 1\n",
    "        for num in nums:\n",
    "            for diff in range(diff_bound_left, diff_bound_right+1):\n",
    "                d[diff][num] = d[diff][num-diff] + 1  # 差对应的长度+1\n",
    "                rs = max(rs, d[diff][num])\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = dict()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            dl = set()\n",
    "            for j in range(i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                dl.add(diff)\n",
    "                if (nums[j], diff) not in dp:\n",
    "                    dp[(nums[j], diff)] = 1\n",
    "            for diff in dl:\n",
    "                dp[(nums[i], diff)] = dp[(nums[i] - diff, diff)] + 1\n",
    "                ans = max(ans, dp[(nums[i], diff)])\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 1 1 0 diff: 41 i: 6 j: 0 53 12\n",
    "# 1 1 0 diff: 25 i: 6 j: 1 53 28\n",
    "# 1 1 0 diff: 40 i: 6 j: 2 53 13\n",
    "# 1 1 0 diff: 47 i: 6 j: 3 53  6\n",
    "# 1 1 0 diff: 19 i: 6 j: 4 53 34\n",
    "# 1 1 0 diff: 17 i: 6 j: 5 53 36\n",
    "\n",
    "# 2 1 0 diff: 41 i: 14 j: 0 53 12\n",
    "# 2 1 0 diff: 25 i: 14 j: 1 53 28\n",
    "# 2 1 0 diff: 40 i: 14 j: 2 53 13\n",
    "# 2 1 0 diff: 47 i: 14 j: 3 53 6\n",
    "# 2 1 0 diff: 19 i: 14 j: 4 53 34\n",
    "# 2 1 0 diff: 17 i: 14 j: 5 53 36\n",
    "# 2 1 1 diff:  0 i: 14 j: 6 53 53\n",
    "# 2 1 0 diff: 29 i: 14 j: 7 53 24\n",
    "# 2 1 0 diff: 24 i: 14 j: 8 53 29\n",
    "# 2 1 0 diff: 51 i: 14 j: 9 53 2\n",
    "# 2 1 0 diff: 30 i: 14 j: 10 53 23\n",
    "# 2 1 0 diff: 53 i: 14 j: 11 53 0\n",
    "# 2 1 0 diff: 31 i: 14 j: 12 53 22\n",
    "# 2 1 0 diff: 28 i: 14 j: 13 53 25\n",
    "\n",
    "# 2 1 0 diff: 41 i: 20 j: 0 53 12\n",
    "# 2 1 0 diff: 25 i: 20 j: 1 53 28\n",
    "# 2 1 0 diff: 40 i: 20 j: 2 53 13\n",
    "# 2 1 0 diff: 47 i: 20 j: 3 53 6\n",
    "# 2 1 0 diff: 19 i: 20 j: 4 53 34\n",
    "# 2 1 0 diff: 17 i: 20 j: 5 53 36\n",
    "# 2 2 2 diff:  0 i: 20 j: 6 53 53\n",
    "# 2 1 0 diff: 29 i: 20 j: 7 53 24\n",
    "# 2 1 0 diff: 24 i: 20 j: 8 53 29\n",
    "# 2 1 0 diff: 51 i: 20 j: 9 53 2\n",
    "# 2 1 0 diff: 30 i: 20 j: 10 53 23\n",
    "# 2 1 0 diff: 53 i: 20 j: 11 53 0\n",
    "# 2 1 0 diff: 31 i: 20 j: 12 53 22\n",
    "# 2 1 0 diff: 28 i: 20 j: 13 53 25\n",
    "# 2 3 3 diff:  0 i: 20 j: 14 53 53\n",
    "# 3 1 0 diff: 19 i: 20 j: 15 53 34\n",
    "# 3 1 0 diff: 30 i: 20 j: 16 53 23\n",
    "# 3 1 0 diff:  3 i: 20 j: 17 53 50\n",
    "# 3 1 0 diff: 18 i: 20 j: 18 53 35\n",
    "# 3 1 0 diff: 10 i: 20 j: 19 53 43"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        vis = set()\n",
    "        diff = dict() # 记录(公差, 最后一个值): 序列长度\n",
    "        for a in nums:\n",
    "            for v in vis:\n",
    "                k = (a - v, v)\n",
    "                if k not in diff:\n",
    "                    diff[k] = 1\n",
    "                diff[(a - v, a)] = diff[k] + 1\n",
    "            vis.add(a)\n",
    "        return max(diff.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: list[int]) -> int:\n",
    "        n = len(nums)\n",
    "        where = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            where[num].append(i)\n",
    "        dp = {}\n",
    "        for k in range(2, n):\n",
    "            c = nums[k]\n",
    "            for j in range(1, k):\n",
    "                b = nums[j]\n",
    "                a = b + b - c\n",
    "                ii = bisect.bisect_left(where[a], j)\n",
    "                if ii != 0:\n",
    "                    i = where[a][ii - 1]\n",
    "                    dp[(j, k)] = dp.get((i, j), 2) + 1\n",
    "        if not dp:\n",
    "            return 2\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                dp[(i, nums[i] - nums[j])] = max(2, dp.get((j, nums[i] - nums[j]), -1) + 1)\n",
    "                ans = max(ans, dp[(i, nums[i] - nums[j])])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dp = {}\n",
    "        n = len(nums)\n",
    "        max_len = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                if (j, diff) in dp:\n",
    "                    dp[(i, diff)] = dp[(j, diff)] + 1\n",
    "                else:\n",
    "                    dp[(i, diff)] = 2\n",
    "                max_len = max(max_len, dp[i, diff])\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        L= len(nums)\n",
    "        dic = {}\n",
    "        dp = {}\n",
    "        maxN = 2\n",
    "        for i in range(L):\n",
    "            for j in range(i+1,L):\n",
    "                ak = 2*nums[i] - nums[j]\n",
    "                if ak in dic:\n",
    "                    dp[(i,j)] = dp.get((dic[ak],i),2) + 1\n",
    "                    maxN = max(maxN,dp[(i,j)])\n",
    "            dic[nums[i]] = i\n",
    "        return maxN\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        maxi = 2003\n",
    "        maxj = 10009 * 2\n",
    "        mod = 10001\n",
    "        dparr = {}\n",
    "\n",
    "        maxn = 0\n",
    "\n",
    "        for i, a in enumerate(A):\n",
    "            if i==0:\n",
    "                continue\n",
    "            else:\n",
    "                for j,b in enumerate(A):\n",
    "                    if j == i:\n",
    "                        break\n",
    "                    else:\n",
    "                        ans = dparr.get((j,a-b+mod), 1) + 1\n",
    "                        dparr[i,a-b+mod] = ans\n",
    "                        if ans > maxn:\n",
    "                            maxn = ans\n",
    "\n",
    "        return maxn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        longest = 2\n",
    "        if n == 2:\n",
    "            return longest\n",
    "        dp = [[None for __ in range(n)] for __ in range(n)]\n",
    "        previous = {}\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = (2, nums[j] - nums[i])\n",
    "                else:\n",
    "                    k = nums[j] - nums[i]\n",
    "                    if nums[i] - k in previous:\n",
    "                        dp[i][j] = (dp[previous[nums[i] - k]][i][0] + 1, k)\n",
    "                    else:\n",
    "                        dp[i][j] = (2, k)\n",
    "\n",
    "                if dp[i][j][0] > longest:\n",
    "                    longest = dp[i][j][0]\n",
    "\n",
    "            previous[nums[i]] = i\n",
    "\n",
    "        return longest\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        n = len(A)\n",
    "        pos = {}\n",
    "        for i, num in enumerate(A):\n",
    "            if num not in pos:\n",
    "                pos[num] = [i]\n",
    "            else:\n",
    "                pos[num].append(i)\n",
    "        r = 1\n",
    "        table = {}\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                r = max(r, self.search(A, j, A[j] - A[i], table, pos) + 1)\n",
    "        return r\n",
    "\n",
    "\n",
    "    def search(self, nums, i, diff, table, pos):\n",
    "        if (i, diff) in table:\n",
    "            return table[(i, diff)]\n",
    "        n = len(nums)\n",
    "        if i == n - 1:\n",
    "            return 1\n",
    "        r = 1\n",
    "        if diff + nums[i] in pos:\n",
    "            for p in pos[diff + nums[i]]:\n",
    "                if p <= i:\n",
    "                    continue\n",
    "                else:\n",
    "                    r = max(r, self.search(nums, p, diff, table, pos) + 1)\n",
    "                    break\n",
    "        table[(i, diff)] = r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        # 两种想法 一种是站在一个index,然后选一个diff 向后找等差数列的数字 太难太暴力\n",
    "        # 第二种就是站在index 选定一个diff 向前继承前面等差数列的数字 dp\n",
    "        # dp[diff][index] means the length of arithmetic sequence at index with difference diff\n",
    "        # dp没办法提前确定大小，用字典来装\n",
    "        dp = {}\n",
    "        for i in range(len(A)):\n",
    "            for j in range(i + 1, len(A)):\n",
    "                dp[j, A[j] - A[i]] = 1 + dp.get((i, A[j] - A[i]), 1)\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        # 和上一题给定等差的值思路类似，不同之处在于这一题最长等差数列的差要自己找，那么就需要O(n^2)\n",
    "        # \n",
    "        n = len(nums)\n",
    "        dp = {}\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                # 在 Python 中，字典的键可以是任何不可变的类型，包括元组。\n",
    "                # 所以 dp[i, j] 实际上是查找键为元组 (i, j) 的值。\n",
    "                # 在这个例子中，dp[j, nums[j] - nums[i]] 表示的是：\n",
    "                # 以 nums[i] 结尾，差为 nums[j] - nums[i] 的等差数列的长度\n",
    "                dp[j, nums[j] - nums[i]] = dp.get((i, nums[j] - nums[i]), 1) + 1\n",
    "                # dp.get(key, default) 函数查找键为 key 的值，如果不存在 key，则返回默认值\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(idx):\n",
    "            max_len={}\n",
    "            for i in range(idx+1,n):\n",
    "                d=nums[i]-nums[idx]\n",
    "                if d not in max_len:\n",
    "                    max_len[d]=dfs(i).get(d,1)+1\n",
    "            return max_len\n",
    "        # print(dfs(0))\n",
    "        return max(max(dfs(i).values()) for i in range(0, n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        len1 = len(nums)\n",
    "        dic1 = {} ## diff,[(start,end)]\n",
    "\n",
    "        for i in range(len1):\n",
    "            for j in range(len1-1,i,-1):\n",
    "                if nums[j]-nums[i] not in dic1:\n",
    "                    dic1[nums[j]-nums[i]] = []\n",
    "                dic1[nums[j]-nums[i]].append([i,j])\n",
    "        \n",
    "        res = 2\n",
    "        for indexs in dic1.values():\n",
    "            if len(indexs) < res:\n",
    "                continue\n",
    "            dp = [1]*len1\n",
    "            for start,end in indexs:\n",
    "                dp[end] = max(dp[start] + 1,dp[end])\n",
    "                res = max(res,dp[end])\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        len1 = len(nums)\n",
    "        dic1 = {} ## diff,[(start,end)]\n",
    "\n",
    "        for i in range(len1):\n",
    "            for j in range(len1-1,i,-1):\n",
    "                if nums[j]-nums[i] not in dic1:\n",
    "                    dic1[nums[j]-nums[i]] = []\n",
    "                dic1[nums[j]-nums[i]].append([i,j])\n",
    "        \n",
    "        res = 2\n",
    "        for indexs in dic1.values():\n",
    "            dp = [1]*len1\n",
    "            for start,end in indexs:\n",
    "                dp[end] = max(dp[start] + 1,dp[end])\n",
    "                res = max(res,dp[end])\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self,):\n",
    "        self.dic = {} ## 起点index diff值 含起点\n",
    "\n",
    "\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        len1 = len(nums)\n",
    "        dic1 = {} ## diff,[(start,end)]\n",
    "\n",
    "        for i in range(len1):\n",
    "            for j in range(len1-1,i,-1):\n",
    "                if nums[j]-nums[i] not in dic1:\n",
    "                    dic1[nums[j]-nums[i]] = []\n",
    "                dic1[nums[j]-nums[i]].append([i,j])\n",
    "        \n",
    "        res = 2\n",
    "        for indexs in dic1.values():\n",
    "            dp = [1]*len1\n",
    "            for start,end in indexs[::-1]:\n",
    "                dp[start] = max(dp[end] + 1,dp[start])\n",
    "                res = max(res,dp[start])\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return len(nums)\n",
    "        # dp[i] is a dict, in which key is the gap of the arithemtic that ends with nums[i]\n",
    "        dp = [collections.defaultdict(list) for _ in range(len(nums))]\n",
    "        self.ans = 2\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            curr = nums[i]\n",
    "            for j in range(i):\n",
    "                pre = nums[j]\n",
    "                # the gap in arithmetic\n",
    "                key = pre - curr\n",
    "                # no arithemtic that ends with nums[j], has a gap == key\n",
    "                if len(dp[j][key]) == 0:\n",
    "                    dp[i][key] = [pre, curr]\n",
    "                else:\n",
    "                    dp[i][key] = dp[j][key] + [curr]\n",
    "                    self.ans = max(self.ans, len(dp[i][key]))\n",
    "        \n",
    "        return self.ans\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            has={}\n",
    "            nonlocal ans\n",
    "            for j in range(i-1,-1,-1):\n",
    "                a=nums[i]-nums[j]\n",
    "                #has[a]=1\n",
    "                q=dfs(j)\n",
    "                if a not in has: \n",
    "                    #q[a]=1\n",
    "                    has[a]=1+q.get(a,1)\n",
    "                else:\n",
    "                    has[a]=max(has[a],1+q.get(a,1))\n",
    "                if ans<has[a]: ans=has[a]\n",
    "            return has\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        dfs(n-1) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int) -> dict[int: int]:\n",
    "            d_len = dict()\n",
    "            for j in range(i-1, -1, -1):\n",
    "                d = nums[i] - nums[j]\n",
    "                if d not in d_len:\n",
    "                    d_len[d] = dfs(j).get(d, 1) + 1\n",
    "            return d_len\n",
    "        return max(max(dfs(i).values()) for i in range(len(nums)-1, 0, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            cnt = Counter()\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                d = nums[i] - nums[j]\n",
    "                if d not in cnt:\n",
    "                    cnt[d] = dfs(j).get(d, 1) + 1\n",
    "            return cnt\n",
    "        return max(max(dfs(i).values()) for i in range(1, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        q = deque()\n",
    "        queued = {}\n",
    "        n = len(nums)\n",
    "\n",
    "        pos_by_num = {}\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            pos = pos_by_num.get(num, [])\n",
    "            pos.append(i)\n",
    "            pos_by_num[num] = pos\n",
    "        \n",
    "        max_len = 2\n",
    "        for k in pos_by_num:\n",
    "            max_len = max(max_len, len(pos_by_num[k]))\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                num_1 = nums[i]\n",
    "                num_2 = nums[j]\n",
    "                step = num_2 - num_1\n",
    "                if step == 0: continue\n",
    "                if queued.get((j, step)) != None: continue\n",
    "\n",
    "                queued[(j, step)] = 2\n",
    "                q.append((j, step, 2))\n",
    "        \n",
    "        while q:\n",
    "            idx, step, arr_len = q.popleft()\n",
    "            num = nums[idx]\n",
    "            next_num = num + step\n",
    "\n",
    "            pos = pos_by_num.get(next_num)\n",
    "            if not pos:\n",
    "                max_len = max(max_len, arr_len)\n",
    "                continue\n",
    "            \n",
    "            x = bisect.bisect_left(pos, idx)\n",
    "            if x == len(pos):\n",
    "                max_len = max(max_len, arr_len)\n",
    "                continue\n",
    "            \n",
    "            next_idx = pos[x]\n",
    "            if queued.get((next_idx, step), 0) >= arr_len + 1:\n",
    "                continue\n",
    "            queued[(next_idx, step)] = arr_len + 1\n",
    "\n",
    "            q.append((next_idx, step, arr_len + 1))\n",
    "        \n",
    "        return max_len\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        len_nums = len(nums)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            counter = Counter()\n",
    "            for j in range(i-1, -1, -1):\n",
    "                gap = nums[i]-nums[j]\n",
    "                if gap not in counter.keys():\n",
    "                    counter[gap] = dfs(j)[gap] + 1\n",
    "            return counter\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len_nums):\n",
    "            temp = dfs(i)\n",
    "            res = max(res, max(temp.values())) if temp!={} else res \n",
    "\n",
    "        return res+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        rec = {}\n",
    "        for i in range(n-1):\n",
    "            v = nums[i]\n",
    "            rec[i] = {}\n",
    "            for j in range(i+1,n):\n",
    "                nv = nums[j]\n",
    "                d = nv-v\n",
    "                if d not in rec[i]:\n",
    "                    rec[i][d] = []\n",
    "                rec[i][d].append(j)\n",
    "        dp = {}\n",
    "        for i in range(n-2,-1,-1):\n",
    "            v = nums[i]\n",
    "            dp[i] = {}\n",
    "            for j in range(n-1,i,-1):\n",
    "                nv = nums[j]\n",
    "                d = nv-v\n",
    "                key = i*n+j\n",
    "                dp[i][d] = max(dp[i].get(d,0),2)\n",
    "                dp[i][d] = max(dp[i][d],dp.get(j,{}).get(d,0)+1)\n",
    "        # maxone = 0\n",
    "        # for key in dp.keys():\n",
    "        #     # maxone = max(maxone,max(list(rec[key].values())))\n",
    "        #     print(dp[key].values(),list(dp[key].values()),max(list(dp[key].values())))\n",
    "        # return maxone\n",
    "        return max([max(list(dp[key].values())) for key in dp.keys()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            max_len = {}\n",
    "            for j in range(i+1,len(nums)):\n",
    "                d = nums[j] - nums[i]\n",
    "                if d not in max_len:\n",
    "                    max_len[d] = dfs(j).get(d,1) + 1\n",
    "            return max_len\n",
    "        return max(max(dfs(i).values()) for i in range(len(nums)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n, ans = len(nums), 0\n",
    "        @cache\n",
    "        def dfs(i) -> {}:\n",
    "            nonlocal ans\n",
    "            max_len = {}\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                d = nums[i] - nums[j]\n",
    "                if d not in max_len:\n",
    "                    max_len[d] = dfs(j).get(d, 1) + 1\n",
    "                    ans = max(ans, max_len[d])\n",
    "            return max_len\n",
    "        dfs(n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        #dp[i][j]: 以第i个数结尾，公差为j的最大长度\n",
    "        #dp[i][j] = max(dp[k][j]) + 1;  nums[i] = nums[k] + j,\n",
    "        # min(nums) - max(nums) <= j <= min(nums) - max(nums)\n",
    "        index = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x not in index:\n",
    "                index[x] = []\n",
    "            index[x].append(i)\n",
    "\n",
    "        longest = collections.defaultdict(lambda: 1)\n",
    "        s, e = (min(nums) - max(nums), max(nums) - min(nums))\n",
    "        tmax = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(s, e+1):\n",
    "                repeat = index.get(nums[i] - j, None)\n",
    "                if repeat is None:\n",
    "                    continue\n",
    "                for k in repeat:\n",
    "                    if k < i:\n",
    "                        longest[i, j] = max(longest[i,j], longest[k, j] + 1)\n",
    "                        tmax = max(longest[i, j], tmax)\n",
    "        return tmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        diff=max(nums)-min(nums)\n",
    "        dp={}\n",
    "        count=0\n",
    "        for i in range(n):\n",
    "            for j in range(-diff,diff+1,1):\n",
    "                if (nums[i]-j,j) in dp:\n",
    "                    dp[(nums[i],j)]=dp[(nums[i]-j,j)]+1\n",
    "                else:\n",
    "                    dp[(nums[i],j)]=1\n",
    "                count=max(count,dp[(nums[i],j)])\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, A: List[int]) -> int:\n",
    "        import collections\n",
    "        from bisect import bisect_left\n",
    "        def find_lt(a, x):\n",
    "            'Find rightmost value less than x'\n",
    "            i = bisect_left(a, x)\n",
    "            if i:\n",
    "                return a[i - 1]\n",
    "            raise ValueError\n",
    "        if len(A) < 3:\n",
    "            return len(A)\n",
    "        index_map = collections.defaultdict(lambda: [])\n",
    "        for i in range(len(A)):\n",
    "            index_map[A[i]].append(i)\n",
    "        longest = collections.defaultdict(lambda: 2)\n",
    "        max_length = -math.inf\n",
    "        for i in range(0, len(A)):\n",
    "            for j in range(0, i):\n",
    "                if j == 0:\n",
    "                    longest[i, j] = 2\n",
    "                else:\n",
    "                    idxs = index_map.get(2 * A[j] - A[i])\n",
    "                    if idxs is not None and len(idxs) > 0:\n",
    "                        if j <= idxs[0]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            idx = find_lt(idxs, j)\n",
    "                            longest[i, j] = max(longest[j, idx] + 1, longest[i, j])\n",
    "                    else:\n",
    "                        longest[i, j] = 2\n",
    "                max_length = max(max_length, longest[i, j])\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[1 for _ in range(10001)] for _ in range(n)]\n",
    "        res = 1\n",
    "        for i in range(n):\n",
    "            for k in range(i):\n",
    "                j = nums[i] - nums[k] + 500\n",
    "                dp[i][j] = max(dp[i][j], dp[k][j] + 1)\n",
    "                res = max(res, dp[i][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dicc=defaultdict(lambda: 1)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                diff=nums[i]-nums[j]\n",
    "                dicc[(diff,i)]=dicc[(diff,j)]+1\n",
    "        return max(dicc.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        dp = defaultdict(int)\n",
    "        maxlen = 1\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            for j in range(i):\n",
    "                diff = nums[i]-nums[j]\n",
    "                dp[(diff,i)] = max(dp[(diff,i)], dp[(diff,j)] + 1)\n",
    "                maxlen = max(maxlen,dp[(diff,i)])\n",
    "\n",
    "        return maxlen + 1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        dp = defaultdict(int)\n",
    "\n",
    "        for i in range(len(nums)) :\n",
    "            for j in range(0, i) :\n",
    "                dp[(i, nums[i]-nums[j])] = dp[(j, nums[i]-nums[j])] + 1\n",
    "        return max(dp.values())+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(ix):\n",
    "            max_len = {}\n",
    "            for i in range(ix -1, -1, -1):\n",
    "                d = nums[i] - nums[ix]\n",
    "                if d not in max_len:\n",
    "                    max_len[d] = dfs(i).get(d, 1) + 1\n",
    "            return max_len\n",
    "        return max(max(dfs(i).values()) for i in range(1, len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, nums: List[int]) -> int:\n",
    "        pos = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in pos:\n",
    "                pos[nums[i]].append(i)\n",
    "            else:\n",
    "                pos[nums[i]] = [i]\n",
    "\n",
    "        dp = dict()\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                dp[(i, j)] = 2\n",
    "\n",
    "        ans = 2\n",
    "        #print(pos)\n",
    "        for i in range(2, len(nums)):\n",
    "            for j in range(1, i):\n",
    "                target = nums[j] - (nums[i] - nums[j])\n",
    "                if target not in pos:\n",
    "                    dp[(j, i)] = 2\n",
    "                else:\n",
    "                    target_lis = pos[target]\n",
    "                    legal_target_lis = target_lis[:bisect.bisect_left(target_lis, j)]\n",
    "                    if legal_target_lis == []:\n",
    "                        dp[(j, i)] = 2\n",
    "                    else:\n",
    "                        k = legal_target_lis[-1]\n",
    "                        dp[(j, i)] = dp[(k, j)] + 1\n",
    "                    ans = max(ans, dp[(j, i)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestArithSeqLength(self, a: List[int]) -> int:\n",
    "        @cache  # 缓存装饰器，避免重复计算 dfs 的结果\n",
    "        def dfs(i: int) -> dict[int, int]:\n",
    "            # i=0 时不会进入循环，返回空哈希表\n",
    "            max_len = {}\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                d = a[i] - a[j]  # 公差\n",
    "                if d not in max_len:\n",
    "                    max_len[d] = dfs(j).get(d, 1) + 1\n",
    "            return max_len\n",
    "        return max(max(dfs(i).values()) for i in range(1, len(a)))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
